package _1024_Video_Stitching;

import java.util.Arrays;

/**
 * Date: 2020/10/24 10:22
 * Content: 区间覆盖问题
 */
public class Solution {

    public int videoStitching(int[][] clips, int T) {

        Arrays.sort(clips, (a, b) -> a[0] - b[0]);

        int res = 0, last = 0;
        for (int i = 0; i < clips.length; ) {
            if (clips[i][0] > last) return -1;

            int r = 0;
            while (i < clips.length && clips[i][0] <= last) {
                r = Math.max(r, clips[i][1]);
                i++;
            }

            last = r;
            res++;
            if (last >= T) break;
        }
        if (last >= T) return res;
        return -1;
    }

    public static void main(String[] args) {

        int[][] clips = {{0, 2}, {4, 8}};
        System.out.println((new Solution()).videoStitching(clips, 5));
    }
}
